package sword.chapter3String;

import java.util.HashMap;

/**
 * 不含重复字符的最长子字符串
 * 输入一个字符串，求该字符串中不含重复字符的最长连续子字符串的长度。例如，输入字符串"babcca"，它最长的不含重复字符串的子字符串是"abc"，长度为3。
 * 要点：
 * 1. map记录不重复字母的最新下标
 * 2. 存在重复字母，比较最新start
 * @author K
 * @date 2021-11-13 15:49
 */
public class S16lengthOfLongestSubstring {
    public static void main(String[] args) {
        String s = "babcca";
        int result = s16lengthOfLongestSubstring(s);
//        int result = lengthOfLongestSubstring(s);
        System.out.println(result);
    }

    public static int s16lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int start = 0;
        int maxLength = 0;
        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                start = Math.max(map.get(c), start);
            }
            maxLength = Math.max(end - start, maxLength);
            map.put(c, end);
        }
        return maxLength;
    }

    public static int lengthOfLongestSubstring(String s) {
        int[] counts = new int[256];
        int longest = s.length() > 0 ? 1 : 0;
        for (int i = 0, j = -1; i < s.length(); ++i) {
            counts[s.charAt(i)]++;
            while (hasGreaterThan1(counts)) {
                ++j;
                counts[s.charAt(j)]--;
            }

            longest = Math.max(i - j, longest);
        }

        return longest;
    }

    private static boolean hasGreaterThan1(int[] counts) {
        for (int count : counts) {
            if (count > 1) {
                return true;
            }
        }

        return false;
    }
}
